package unionfind;

/**
 * @author pengfei.hpf
 * @date 2020/2/27
 * @verdion 1.0.0
 * 给定从 0 到 n-1 标号的 n 个结点，和一个无向边列表（每条边以结点对来表示），请编写一个函数用来判断这些边是否能够形成一个合法有效的树结构。
 *
 * 示例 1：
 *
 * 输入: n = 5, 边列表 edges = [[0,1], [0,2], [0,3], [1,4]]
 * 输出: true
 * 示例 2:
 *
 * 输入: n = 5, 边列表 edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
 * 输出: false
 * 注意：你可以假定边列表 edges 中不会出现重复的边。由于所有的边是无向边，边 [0,1] 和边 [1,0] 是相同的，因此不会同时出现在边列表 edges 中。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/graph-valid-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ValidTree {
    public boolean validTree(int n, int[][] edges) {
        if(n == 0 || edges == null || edges.length == 0 || edges[0].length == 0){
            return false;
        }
        int[] par = new int[n];
        for(int i = 0; i < n; i++){
            par[i] = i;
        }
        for(int i = 0; i < edges.length; i ++){
            if(!union(par, edges[i][0], edges[i][1])){
                return false;
            }
        }
        int count = 0;
        for(int i = 0; i < n; i ++){
            if(par[i] == i){
                count ++;
            }
        }

        return count ==1;
    }

    private int find(int[] par, int num){
        int root = num;
        while(par[root] != root){
            root = par[root];
        }
        par[num] = root;
        return root;
    }

    private boolean union(int[] par, int a, int b){
        int aroot = find(par, a);
        int broot = find(par, b);
        if(aroot == broot){
            return false;
        }
        if(aroot < broot){
            par[broot] = aroot;
        } else {
            par[aroot] = broot;
        }
        return true;
    }

    public static void main(String[] args){

    }
}
